package LeetCode.interview;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

import com.sun.org.apache.bcel.internal.generic.IF_ACMPEQ;
import com.sun.org.apache.xpath.internal.operations.Number;

import LeetCode.interview._104_Maximum_Depth_of_Binary_Tree.TreeNode;
import sun.tools.jar.resources.jar;
import util.LogUtils;

/*
 * 
原题　
			House Robber II
	
	Note: This is an extension of House Robber.
	
	After robbing those houses on that street, the thief has found himself a new place for his thievery so that he will not get too much attention. This time, all houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, the security system for these houses remain the same as for those in the previous street.
	
	Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.
	
	Credits:
	Special thanks to @Freezen for adding this problem and creating all test cases.

题目大意
		
解题思路
	House Robber I的升级版. 因为第一个element 和最后一个element不能同时出现. 则分两次调用  House Robber I. 
		case 1: 不包括最后一个element. 
		case 2: 不包括第一个element.	
   
   @Type 动态规划
 * @Date 2017-10-29 11：25
 */
public class _213_House_Robber_II {
	
    public int rob(int[] nums) {
    	if (nums==null || nums.length==0)	return 0;
    	int N = nums.length;
    	if (nums.length == 1)	return nums[0];
    	if (nums.length == 2)	return Math.max(nums[0], nums[1]);
		return Math.max(subRob(nums, 0, N-2), subRob(nums, 1, N-1));
    }
    
    public int subRob(int[] nums, int start, int end) {
    	int N = end-start+1;
    	int[] dp = new int[N];
    	dp[0] = nums[start];
    	dp[1] = Math.max(nums[start], nums[start+1]);
    	for (int i = 2; i < N; i ++) {
    		dp[i] = Math.max(dp[i-2]+nums[i+start], dp[i-1]);
    	}
    	return dp[N-1];
    }
    
	public static void main(String[] args) {
		_213_House_Robber_II obj = new _213_House_Robber_II();
		LogUtils.println("213题：", obj.rob(new int[]{4, 3, 1, 3, 2}));
	}

}
